'''
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
'''

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        slow,fast = head,head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        mid = slow.next
        slow.next = None
        left,right = self.sortList(head),self.sortList(mid)
        # cur =  t = ListNode()
        # while left and right:
        #     if left.val < right.val:
        #         cur.next = left
        #         left = left.next
        #     else:
        #         cur.next = right
        #         right  = right.next
        #     cur = cur.next
        # cur.next = left if left else right
        # return t.next
        t = self.mergeTwoLists(left,right)
        return t
    def mergeTwoLists(self,list1:ListNode, list2:ListNode):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        newList = ListNode(-1)
        temp = newList
        p = list1
        q = list2
        while p and q:
            if p.val > q.val:
                temp.next = q
                q = q.next
            else:
                temp.next = p
                p = p.next
            temp = temp.next
        if p:
            temp.next = p
        if q:
            temp.next = q
    
        return newList.next 